✎ Couple de Bézout en « remontant » l'algorithme d'Euclide - Méthode

On souhaite déterminer un couple $(u;v)\in {\mathbb{Z}}^2$ tel que $8u+19v=1$ . Pour cela, on peut « remonter » l'algorithme d'Euclide appliqué à  $19$  et  $8$ .

L'idée principale est que l'égalité  $8u+19v=1$  est une manière d'écrire $1$  (autrement dit, le PGCD de $8$  et $19$ ) comme une combinaison linéaire de  $8$  et  $19$ .

Pour obtenir une telle égalité, on peut additionner les lignes obtenues dans l'algorithme d'Euclide, à condition d'éliminer tous les diviseurs  $b$ et restes  $r$ intermédiaires.

Étant donné qu'un diviseur  $b$  donné est le reste  $r$  de la ligne précédente, il s'agit en fait d'éliminer tous les restes intermédiaires dans l'algorithme d'Euclide, excepté le PGCD. Pour cela, avant d'additionner les lignes de l'algorithme d'Euclide, on doit multiplier chacune d'entre elles par un coefficient choisi de manière à supprimer ces restes intermédiaires.

Voici une manière de remonter l'algorithme d'Euclide appliqué à  $19$  et  $8$  :

$\begin{array}{r}\begin{array}{c}\\ L_1\\ L_2\\ L_3\\ \end{array}\begin{array}{|cccc|}\hline a& b& q& r\\ 19& 8& 2& 3\\ 8& 3& 2& 2\\ 3& 2& 1& 1\\ 2& 1& 2& 0\\ \hline\end{array}\begin{array}{ll}& \\ \times 3& \text{suppression du reste }3\\ \times (-1)& \text{suppression du reste }2\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{array}$   

• Pour conserver le PGCD (égal à $1$  dans cet exemple), on multiplie la ligne  $L_3$ par  $1$ .
  La ligne  $L_3$  devient donc :  $3\times 1=2\times 1\times 1+1\times 1$ .
  
• Pour supprimer le reste  $2$  sur la ligne  $L_2$ , on tient compte que ce reste  $2$  apparaît dans le produit  $2\times 1\times 1$  de la ligne  $L_3$ . Afin que  $2$  disparaisse en additionnant les ligne  $L_3$  et  $L_2$ , il faut donc multiplier la ligne  $L_2$  par  $-1$  (car  $2$  apparaît « une fois côté diviseur » sur la ligne  $L_3$ ).
  La ligne  $L_2$  devient donc :  $8\times (-1)=3\times 2\times (-1)+2\times (-1)$ .
  
• Pour éliminer le reste  $3$  sur la ligne  $L_1$ , on tient compte que ce reste  $3$  apparaît dans le produit  $3\times 2\times (-1)$  de la ligne  $L_2$  et dans le produit  $3\times 1$  de la ligne  $L_3$ .
  Afin que  $3$  disparaisse en additionnant les lignes  $L_3$ ,  $L_2$  et  $L_1$ , il faut donc multiplier la ligne  $L_1$  par  $3$  (car  $3$  apparaît « une fois côté dividende » sur la ligne  $L_3$  et « moins deux fois côté diviseur » sur la ligne  $L_2$ ).
  La ligne  $L_1$  devient donc :  $19\times 3=8\times 2\times 3+3\times 3$ .
  

En additionnant les lignes  $L_1$ ,  $L_2$  et  $L_3$  modifiées, on a donc :
$\begin{array}{r}\begin{array}{lrcllcl}& 19\times 3& =& & 8\times 2\times 3& +& 3\times 3\\ +& 8\times (-1)& & +& 3\times 2\times (-1)& +& 2\times (-1)\\ +& 3\times 1& & +& 2\times 1\times 1& +& 1\times 1\end{array}\end{array}$  
autrement dit, après simplifications,
$\begin{array}{rl}19\times 3+8\times (-1)=8\times 2\times 3+1& ⟺8\times (-7)+19\times 3=1\end{array}$ donc le couple $(u;v)=(-7;3)$ convient pour satisfaire l'égalité  $8u+19v=1$ .